(1) Field of the Invention
The present invention relates to a computation processing technique using an elliptic curve, and in particular relates to a technique for countering Differential Fault Attack (DFA).
(2) Description of the Related Art
Public key cryptography has conventionally been known as a method for realizing confidentiality of information, authentication of information, etc.
According to public key cryptography, a pair of a secret key exclusively held by the user and a public key that is made public is generated. Encryption is performed using the public key, and decryption is performed using the secret key.
Despite its large amount of computation processing, public key cryptography, which does not require a secret key to be shared by a plurality of users, is often employed in such applications that require high security. Typical examples of public key cryptography include RSA cryptography and elliptical curve cryptography.
The security of public key cryptography is based on the discrete logarithm problem. Typical examples of the discrete logarithm problem are problems defined over finite fields and problems defined over elliptic curves. Here, the following describes a discrete logarithm problem defined over an elliptic curve. Assume that E(GF(p)) is an elliptic curve defined over a finite field GF(p), with an element G on the elliptic curve E being set as a base point when the order of the elliptic curve E is exactly divided by a large prime. In this case, the discrete logarithm problem is to compute an integer x, if any, that satisfies the equation;
Y=x*G, where Y is a given element on the elliptic curve E.
Here, pis a prime and GF(p) is a finite field that includes p elements. In this specification, the symbol “*” represents repeated additions of a point, i.e., an element, on the elliptic curve, and such computation involving “*” is referred to as the “computation of an elliptic curve exponentiation”.
The security of public key cryptography is based on extreme difficulty of the discrete logarithm problem for the finite field GF(p) including a large number of elements.
For public key cryptography, a secret key is usually held by such means as an IC card that does not allow revealing of the key to third parties.
With the technique described above, secret information can be transmitted without being revealed to third parties. However, Japanese Laid-Open Patent Application No. 2002-261751 refers to the emergence of attacks of unauthorized obtaining of secret information by analyzing various information output from an IC card or the like. One type of such attacks is the DFA.
The DFA is made by a third party intentionally causing a failure in an IC card that is being engaged in decryption processing, by applying overcurrent or the like. The IC card then outputs a value that had been computed before the occurrence of the failure. The third party collects a large number of values output from the IC card by repeating this. The third party then obtains secret information by analyzing the collected values.
To counter this problem, Japanese Laid-Open Patent Application No. H11-8616 discloses an IC card particularly designed to deal with the DFA. This IC card includes a coprocessor, and can realize rapid processing of exponential remainder computation for generating digital signature according to RSA cryptography, by Chinese remainder theorem, using a prime factor of a public key n. This IC card can compute, at the same time with data generated in the computation process of Chinese remainder theorem, error-detecting code for the data. The IC card then can compute error-detecting code again for the data when the digital signature is generated, and compare the computed error-detecting code with the stored error-detecting code.